from tools_algorithm import *
from sortedcontainers import SortedDict


class Solution:
    def findMaximumScore(self, nums: List[int]) -> int:
        h, n = SortedDict(), len(nums)
        ans = 0
        for i, v in enumerate(nums):
            if v not in h.keys():
                j = h.bisect_left(v) - 1
                vi = 0
                if j >= 0:
                    pj, vj = h[h.keys()[j]]
                    vi = vj + (i - pj) * h.keys()[j]
                h[v] = i, vi
                ans = max(ans, vi + (n - 1 - i) * v)
        return ans


s = Solution()
print(s.findMaximumScore(nums=[1, 3, 1, 5]))
print(s.findMaximumScore(nums=[4, 3, 1, 3, 2]))
print(s.findMaximumScore([1, 2, 3, 2, 3, 1]))
